import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-15
 * Time: 21:16
 */
//https://leetcode.cn/problems/valid-triangle-number/
public class Test {
        public static int triangleNumber(int[] arr) {
            Arrays.sort(arr);
            int i,j,k,n=0;
            for( i=arr.length-1;i>=2;i--){
                j=0;
                k=i-1;
                while(j<k){
                    if(arr[j]+arr[k]>arr[i]){
                        n+=k-j;
                        k--;
                    }
                    else{
                        j++;
                    }
                }
            }
            return n;
        }

    public static void main(String[] args) {
        int[] arr={1,23,4,57,8,9,34,1,4,5,678,82,19,23,4,5123,345};
        System.out.println(triangleNumber(arr));
    }
}
